#include <stdio.h>
#include <limits.h>

typedef long int TwoDimArray[5][5];
#define Infinity INT_MAX

/* START: fig10_46.txt */
/* Compute optimal ordering of matrix multiplication */
/* C contains number of columns for each of the N matrices */
/* C[ 0 ] is the number of rows in matrix 1 */
/* Minimum number of multiplications is left in M[ 1 ][ N ] */
/* Actual ordering is computed via */
/* another procedure using LastChange */
/* M and LastChange are indexed starting at 1, instead of 0 */
/* Note: Entries below main diagonals of M and LastChange */
/* are meaningless and uninitialized */

void OptMatrix(const long C[], int N, TwoDimArray M, TwoDimArray LastChange) {
	int i, k, Left, Right;
	long ThisM;

	for (Left = 1; Left <= N; Left++)
		M[Left][Left] = 0;
	for (k = 1; k < N; k++) /* k is Right - Left */
		for (Left = 1; Left <= N - k; Left++) {
			/* For each position */
			Right = Left + k;
			M[Left][Right] = Infinity;
			for (i = Left; i < Right; i++) {
				ThisM = M[Left][i] + M[i + 1][Right]
						+ C[Left - 1] * C[i] * C[Right];
				if (ThisM < M[Left][Right]) /* Update min */
				{
					M[Left][Right] = ThisM;
					LastChange[Left][Right] = i;
				}
			}
		}
}
/* END */

main() {
	long C[] = { 50, 10, 40, 30, 5 };
	long M[5][5], LastChange[5][5];
	int i, j;

	OptMatrix(C, 4, M, LastChange);
	for (i = 1; i <= 4; i++) {
		for (j = 1; j <= 4; j++)
			printf("%14d", M[i][j]);
		printf("\n");
	}
	for (i = 1; i <= 4; i++) {
		for (j = 1; j <= 4; j++)
			printf("%14d", LastChange[i][j]);
		printf("\n");
	}
	return 0;
}

